Package edu.claflin.finder.algo

Class ConnectedComponentsDFS

java.lang.Object

edu.claflin.finder.algo.Algorithm

edu.claflin.finder.algo.ConnectedComponentsDFS

All Implemented Interfaces:

Processable<Graph,Graph>

public class ConnectedComponentsDFS
extends Algorithm

Processes a Graph searching for connected components by performing a depth first search on each node.

Nested Class Summary

Nested classes/interfaces inherited from class edu.claflin.finder.algo.Algorithm

Algorithm.GraphSortOrder

Field Summary

Fields inherited from class edu.claflin.finder.algo.Algorithm

args, counter, listener, PROP_PROGRESS

Constructor Summary

Constructors

Constructor	Description
ConnectedComponentsDFS(ArgumentsBundle bundle)	Public constructor for initializing the DepthFirstTraversalSearch with default conditions.

Method Summary

Modifier and Type	Method	Description
private void	dfs(Node n, java.util.List<Node> inodes, java.util.List<Node> onodes, Graph orig)	Recursive dfs that stores the nodes of a connected component.
private java.util.ArrayList<Graph>	getConnectedComponents(Graph graph)	Gets a list of this Graph's Connected Components.
java.util.ArrayList<Graph>	process(Graph graph)	Processes data.
java.lang.String	toString()

Methods inherited from class edu.claflin.finder.algo.Algorithm

addPropertyChangeListener, cull, getGraphSortOrder, getPartiteNumber, removePropertyChangeListener, setGraphSortOrder, setPartiteNumber, setProgress

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

ConnectedComponentsDFS

public ConnectedComponentsDFS(ArgumentsBundle bundle)

Public constructor for initializing the DepthFirstTraversalSearch with default conditions.

Parameters:

bundle - the ArgumentsBundle containing the instantiation arguments.

Method Detail

process

public java.util.ArrayList<Graph> process(Graph graph)

Processes data.
Finds most Subgraphs by performing a depth first search on the node tree. It is unknown if it finds all or only most of the subgraphs due to the nature of the algorithm. It is expected, however, that it would miss certain node groupings.

Parameters:

graph - the Graph object to search through.

Returns:

the ArrayList of Graph objects holding all found subgraphs.

getConnectedComponents

private java.util.ArrayList<Graph> getConnectedComponents(Graph graph)

Gets a list of this Graph's Connected Components. Uses Depth First Search Technique

Returns:

the list of this Graph's Connected Components

dfs

private void dfs(Node n,
                 java.util.List<Node> inodes,
                 java.util.List<Node> onodes,
                 Graph orig)

Recursive dfs that stores the nodes of a connected component.

Parameters:

n - the starting node

inodes - the nodes awaiting consideration

onodes - the list of nodes to store the nodes of the connected components

orig - original graph (should be undirected)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object